import java.util.LinkedList;
import java.util.List;

/**
 * A Region consists of 4 points. (2 Ranges,int[2][3]{
 * {yStart1,yEnd1,x1},{yStart2,yEnd2,x2} }). <br>
 * A Range consists of 2 points in the single line(int[3]{yStart,yEnd,x}).
 * 
 * @author floyd
 * 
 */
public class ScatterDataRecognizer {

	private byte[][] raw;

	public final static byte VAL_NEGATIVE = 0;

	StringBuilder buffer = new StringBuilder();

	public void init(byte[][] data) {
		raw = data;
	}

	public List<int[][]> recognize() {
		for (int i = 0; i < raw.length; i++) {
			findRegions(i, null);
		}
		return regions;
	}

	List<int[][]> regions = new LinkedList<int[][]>();

	boolean isSamePoint(int[] p1, int[] p2) {
		return (p1[0] == p2[0]) && (p1[1] == p2[1]) && p1[2] == p2[2];
	}

	private void regionOver() {
		if (region != null) {
			if (region[0] != null) {
				if (region[1][1] != 0 && !isSamePoint(region[0], region[1])) {
					for (int i = region[0][2]; i <= region[1][2]; i++) {
						for (int j = region[0][0]; j <= region[0][1]; j++) {
							raw[i][j] = VAL_NEGATIVE;
						}
					}
					regions.add(region);
				}
			}
		}
		region = null;
	}

	private int yAbsentAllowedCount = 2;

	volatile private int xAbsentAllowedCount = 2;

	private int xOffsetAllowedCount = 10;

	private int yOffsetAllowedCount = 10;

	int[][] region;

	private void recordLastRange(int[] lastRange) {
		if (lastRange != null) {
			if (region == null) {
				region = new int[2][3];
				region[0] = null;
			}
			if (region[0] == null) {
				region[0] = lastRange;
			} else {
				if (region[0][1] < lastRange[1]) {
					region[0][1] = lastRange[1];// left
				} /*
				 * else { lastRange[1] = region[0][1]; }
				 */
				if (region[0][0] > lastRange[0]) {
					region[0][0] = lastRange[0];// right
				}/*
				 * else { lastRange[0] = region[0][0]; }
				 */
				region[1] = lastRange;
			}
		}
	}

	int count = 100000;

	private int[] getNextRange(int[] range, int[] lastRange) {
		if (lastRange != null && lastRange[0] > range[1]) {
			return null;
		}
		if (range != null
				&& region != null
				&& (region[0][0] - range[0] > yOffsetAllowedCount || range[1]
						- region[0][1] > yOffsetAllowedCount)) {
			return null;
		}
		return range;
	}

	/**
	 * Find regions with high density of POSITIVE points
	 * 
	 * @param x
	 *            - line number
	 * @param lastRange
	 *            - last range in the recursive stack
	 */
	public void findRegions(int x, int[] lastRange) {
		if (count-- < 0) {
			throw new RuntimeException();
		}

		recordLastRange(lastRange);
		if (x > raw.length - 1) {
			regionOver();
			return;
		}
		int[] range = null;// tmp range found
		if (region == null || x - region[0][2] < xOffsetAllowedCount) {
			for (int y = 0; y < raw[x].length; y++) {
				if (raw[x][y] != VAL_NEGATIVE) {
					// POSITIVE value
					if (range == null) {
						range = new int[] { y, y, x };// range start
					} else {
						range[1] = y;// expand the range
					}
				} else {
					// NEGATIVE value
					if (range != null) {
						// range end check(in-line broken),
						// then find region 'deeper' if allowed
						if (y - range[1] > yAbsentAllowedCount) {
							int[] nextRange = getNextRange(range, lastRange);
							if (nextRange != null) {
								Object regionBefore = region;
								findRegions(x + 1, nextRange);

								if (regionBefore != null && region == null) {
									// Got region-over result,return for
									// performance
									return;
								}
							}
							range = null;
							continue;
						}
					} else if (lastRange != null && y > lastRange[1]) {
						// range never & ever found in line
						// between-line broken check
						break;
					}
				}
			}
			if (range != null) {
				int[] nextRange = getNextRange(range, lastRange);
				if (nextRange != null) {
					findRegions(x + 1, nextRange);
					return;
				} else {
					range = null;
				}
			}
		}

		if (lastRange != null && range == null) {
			if (x - lastRange[2] <= xAbsentAllowedCount) {
				// no range found before,we use latest valid range
				findRegions(x + 1, lastRange);
			} else {
				// sorry ,line broken as follwing:
				// 0000110000
				// ...(no ranges found in 'xAbsentAllowedCount' lines)
				// 0000110...
				regionOver();
			}
		}
	}

	public int getXAbsentAllowedCount() {
		return xAbsentAllowedCount;
	}

	public void setXAbsentAllowedCount(int absentAllowedCount) {
		xAbsentAllowedCount = absentAllowedCount;
	}

	public int getYAbsentAllowedCount() {
		return yAbsentAllowedCount;
	}

	public void setYAbsentAllowedCount(int absentAllowedCount) {
		yAbsentAllowedCount = absentAllowedCount;
	}

	public int getXOffsetAllowedCount() {
		return xOffsetAllowedCount;
	}

	public void setXOffsetAllowedCount(int offsetAllowedCount) {
		xOffsetAllowedCount = offsetAllowedCount;
	}

	public int getYOffsetAllowedCount() {
		return yOffsetAllowedCount;
	}

	public void setYOffsetAllowedCount(int offsetAllowedCount) {
		yOffsetAllowedCount = offsetAllowedCount;
	}
}
